#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <cassert>
#include <cmath>
using namespace std;
class Solution {
public:
	typedef unsigned int uint32;

	int divide(int dividend, int divisor) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function
		assert(0!=divisor);

		if(0==dividend)
			return 0;

		uint32 da,db;

		if(dividend < 0){
			da = (uint32)(dividend ^ -1) + 1;
		}else
			da = dividend;

		if(divisor < 0){
			db = (uint32)(divisor^-1)+1;
		}else
			db = divisor;

		uint32 result = solve(da,db);

		if((dividend<0 && divisor<0) || (dividend>0 && divisor>0))
			return result;
		else
			return int(result^-1)+1;
	}

	int solve(uint32 da,uint32 db){
		if(da < db)
			return 0;
		if(da==db)
			return 1;

		uint32 dd = db;
		uint32 dsum = 0, dcur = 1;

		while(da >= db){
			while(dd < da){
				if((dd<<1) > dd){
					dd <<= 1;
					dcur <<= 1;
				}
				else
					break;
			}

			while(dd > da){
				dd >>= 1;
				dcur >>= 1;
			}
			da -= dd;
			dsum += dcur;
		}

		return dsum;
	}
};
#endif